package tree;
/**
 * @Description
 * @Author Firenut
 * @Date 2023-01-24 11:39
 */
public class T55_II_isBalanced {

    // 法1
    boolean flag = true;
    public boolean isBalanced(TreeNode root) {
        preorder(root, 0);
        return flag;
    }
    //自顶向下求深度(也可以自底向上求深度)
    int preorder(TreeNode node,int count){
        if (node == null) {
            return count;
        }
        count++;
        int left = preorder(node.left, count);//左子树的高度
        if (left == -1) {
            return -1;
        }
        int right = preorder(node.right, count);//右子树的高度
        if (right == -1) {
            return -1;
        }
        if(flag){ //如果flag为true,才有必要继续判断;如果为false,直接退出了
            flag = Math.abs(right - left) <= 1;
            return Math.max(right, left); //取该结点的左子树深度和右子树深度的最大值作为当前结点为根结点的深度
        }else{
            return -1; //返回-1表示非平衡二叉树,避免后序重复计算
        }
    }

    // 法1: 优化
    // 其实可以不用 布尔值flag做标记
    public boolean isBalanced1(TreeNode root) {
        return preorder1(root, 0) != -1;
    }

    int preorder1(TreeNode node,int count){
        if (node == null) {
            return count;
        }
        count++;
        int left = preorder1(node.left, count);//左子树的高度
        if (left == -1) {
            return -1;
        }
        int right = preorder1(node.right, count);//右子树的高度
        if (right == -1) {
            return -1;
        }
        return Math.abs(right - left) <= 1 ? Math.max(right, left) : -1;
    }

    // 法2:自底向上求深度
    public boolean isBalanced2(TreeNode root) {
        return preorder(root) != -1;
    }

    int preorder(TreeNode node){
        if (node == null) {
            return 0;
        }
        int left = preorder(node.left);//左子树的高度
        if (left == -1) {
            return -1;
        }
        int right = preorder(node.right);//右子树的高度
        if (right == -1) {
            return -1;
        }
        return Math.abs(right - left) <= 1 ? Math.max(right, left) + 1 : -1;
    }
}